#include "stack.h"


void Swap(int* p, int* q) {
	int tmp = *p;
	*p = *q;
	*q = tmp;
}
//三数取中 -> 在数组已经有序的情况下提高效率
int select_pit(int *a, int left, int right) {
	int mid = (left + right) / 2;
	mid = a[left] > a[mid] ? (a[left] > a[right] ? right : left) : (a[mid] > a[right] ? mid : right);
	return mid;
}
//挖坑法
void QuickSort1(int* a, int left, int right) {
	if (left >= right) {
		return;
	}
	int index = select_pit(a, left, right);
	Swap(&a[left], &a[index]);
	int begin = left, end = right;
	int key = a[begin];
	int pit = left;

	while (begin < end) {
		while (begin < end && a[end] >= key) {//不能只是大于 -> 数据并不一定只出现一次，假设同时出现2个key，两个相同数换来换去，那程序不就炸了嘛
			--end;
		}
		a[pit] = a[end];
		pit = end;
		while (begin < end && a[begin] <= key) {
			++begin;
		}
		a[pit] = a[begin];
		pit = begin;
	}
	a[pit] = key;
    //分治递归 -> 8 - 4、4 - 2、2、2、2 - 1、1、1、1、1、1、1、1
    //                                                 return◀
	QuickSort1(a, left, pit - 1);
	QuickSort1(a, pit + 1, right);
}

//头尾双指针
int sortpart(int* a, int left, int right) {
	int index = select_pit(a, left, right);
	//Swap(&a[left], &a[index]);
	int begin = left, end = right;
	int key = begin;
//类似二分查找（个人观点）
	while (begin < end) {
		while (begin < end && a[end] >= a[key]) {
			--end;
		}
		while (begin < end && a[begin] <= a[key]) {
			++begin;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[key]);
	return begin;
}
void QuickSort2(int* a, int left, int right) {
	if (left >= right) {
		return;
	}
	int begin = sortpart(a, left, right);
	QuickSort2(a, left, begin - 1);
	QuickSort2(a, begin + 1, right);
}

//非递归
//栈是先进后出，利用栈我们可以从左到右处理数据（不过入栈时记得先右再左）
void QuickSortNone(int* a, int n) {
	ST st;
	Stack_Init(&st);
	Stack_Push(&st, n - 1);
	Stack_Push(&st, 0);

	while (!(Stack_Empty(&st))) {
		int left = Stack_Top(&st);
		Stack_Pop(&st);
		int right = Stack_Top(&st);
		Stack_Pop(&st);

		int key = sortpart(a, left, right);

		if (key + 1 < right) {
			Stack_Push(&st, right);
			Stack_Push(&st, key + 1);
		}

		if (left < key - 1) {
			Stack_Push(&st, key - 1);
			Stack_Push(&st, left);
		}
	}
	Stack_Destory(&st);
}

void print(int *a, int n) {
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

void test1() {
	int a[] = { 1,2,3,5,4,6,7,0,8,9 };
	QuickSort1(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	print(a, sizeof(a) / sizeof(a[0]));
}
void test2() {
	int a[] = { 1,2,3,5,4,6,7,0,8,9 };
	QuickSort2(a, 0, sizeof(a) / sizeof(a[0]) - 1);
	print(a, sizeof(a) / sizeof(a[0]));
}

void test3() {
	int a[] = { 1,2,3,5,4,6,7,0,8,9 };
	QuickSortNone(a, sizeof(a) / sizeof(a[0]));
	print(a, sizeof(a) / sizeof(a[0]));
}

//可以测试某个程序性能
void TestOP()
{
	srand(time(0));
	const int N = 1000000;
	int* a4 = (int*)malloc(sizeof(int) * N);
	int* a5 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a4[i] = rand();
		a5[i] = a4[i];
	}
	int begin4 = clock();
	QuickSortNone(a4, N);
	int end4 = clock();
	int begin5 = clock();
	QuickSort1(a5, 0, N - 1);
	int end5 = clock();
	printf("QuickSortNone:%d\n", end4 - begin4);
	printf("QuickSort1:%d\n", end5 - begin5);
	free(a4);
	free(a5);
}
int main() {
	//test1();
	//test2();
	//test3();
	TestOP();
	return 0;
}